Người Hung Nô cai trị vùng đất Tuva từ trước đó tới năm 200 SCN. Khi đó, một dân tộc có tên gọi trong sử sách Trung Hoa là Đinh Linh đã định cư ở khu vực. Sử sách Trung Hoa ghi nhận sự tồn tại của một bộ lạc có nguồn gốc Đinh Linh tên là Dubo ở phía đông Sayans. Tên gọi này được công nhận có liên hệ với người Tuvan và là những văn bản đầu tiên viết về họ. Tiên Ti đánh bại Hung Nô và họ sau đó lại bị người Nhu Nhiên đánh bại. Từ khoảng cuối thế kỷ 6, người Đột Quyết đã cai trị Tuva cho đến thế kỷ 8 khi người Duy Ngô Nhĩ nắm quyền kiểm soát.

Người Tuvan là thần dân của Hồi Cốt vào thế kỷ 8 và 9. Những người Duy Ngô Nhĩ đã cho lập một số công sự bên trong Tuva. Có một số kế hoạch nhằm khôi phục lại phần còn lại của một trong các thành này là Por-Bazhyn tại hồ Tere-Khol ở đông nam nước cộng hòa.[4] Ký ức về sự chiếm đóng của người Duy Ngô Nhĩ vẫn còn tồn tại cho đến cuối thế kỷ 19 qua tên gọi Duy Ngô Nhĩ Ondar cho những người Tuva Ondar sống gần sông Khemchik ở tây nam.[5] Sự thống trị của người Duy Ngô Nhĩ bị người Kyrgyz Yenisei lật đổ vào năm 840, tức những người từ thượng lưu sông Yenisei. Năm 1207, hoàng thân người Oirat Quduqa-Beki lãnh đạo một đội quân Mông Cổ đến một chi lưu của sông Kaa-Khem. Họ đã chiến đấu với người Tuva Keshdim, Bait, và Telek. Sự kiện này đã đánh dấu thời kỳ người Tuva bị người Mông Cổ nô dịch. Cho đến thế kỷ 17, người Tuva nằm dưới sự kiểm soát của lãnh đạo người Mông Cổ Khalka.

Quốc gia của Altyn-Khan biến mất do chiến tranh liên miên giữa người Oirat và người Khalka của Jasaghtu Khan Aimak. Người Tuvan trở thành một phần của nước Dzungar do người Oirat lãnh đạo. Dzungar kiểm soát toàn bộ cao nguyên Sayano-Altay cho đến năm 1755. Trong giai đoạn Dzungar cầm quyền nhiều bộ tộc và thị tộc đã di chuyển nơi ở và sống xen kẽ nhau. Các nhóm Altayan Telengits sống ở tây Tuva bên bờ các sông Khemchik và Barlyk và tại vùng Bai-Taiga. Một số người Todzhan, Sayan, và Mingat dừng chân tại Altay. Các nhóm Tuva di cư về phía bắc đến dãy Sayan và trở thành Beltir (Dag-Kakpyn, Sug-Kakpyn, Ak-Chystar, Kara-Chystar). Ngôn ngữ của người Beltir và Tuva vẫn có một số từ chung không tìm thấy ở các ngôn ngữ Khaka khác (Kachin và Sagay).[6]